public class Solution {

    public int getHeight(TreeNode node) {
        if (node == null) 
            return 0;
        return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }

    public int deep(TreeNode node) {
        if (node == null) 
            return 0;
        
        int left = deep(node.left);
        if (left == -1)
            return -1;
        
        int right = deep(node.right);
        if (right == -1 || Math.abs(left - right) > 1) 
            return -1;
        
        return Math.max(left, right) + 1;
    }

    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null)
            return true;

        // 递归
        /*
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right) && Math.abs(getHeight(root.left) - getHeight(root.right)) < 2;
        */

        // 回溯
        return deep(root) != -1;
    }
}